# 首先，我们要明确动态规划在这里的作用。我们试图建立一个二维数组，这个数组的每一个值 dp[i][j] 都代表了从字符串的第 i 位到第 j 位之间的最长回文子序列的长度。
#
# 现在，考虑下面这种情况：假设我们正在查找从 i 到 j 的子串，并且子串的两端字符相同，即 s[i] == s[j]。在这种情况下，我们知道这两个字符可以成为一个回文子序列的一部分。
# 但问题是，我们如何确定这两个字符之间的子串的最长回文子序列长度呢？
#
# 答案是：我们已经在前面的计算中找到了从 i+1 到 j-1 的子串的最长回文子序列长度。
# 为什么是从 i+1 到 j-1 呢？因为我们已经确定 s[i] 和 s[j] 可以构成回文的一部分，所以我们只需要知道它们之间的子串的最长回文子序列长度。这就是 dp[i+1][j-1] 的值。
#
# 因此，我们可以得出以下结论：如果 s[i] == s[j]，那么从 i 到 j 的子串的最长回文子序列长度是 dp[i+1][j-1] + 2。其中的 "+2" 是因为我们加入了两个字符 s[i] 和 s[j]。

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

# 示例测试
print(longest_palindromic_subsequence("bbbab"))  # 输出: 4
print(longest_palindromic_subsequence("cbbd"))   # 输出: 2
